package com.demo.java.OD301_350.OD308;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des：【宜居星球改造计划】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146103975
 */
public class OdMain {
    // 记录矩阵的行数和列数
    private static int rows;
    private static int cols;

    // 复制的矩阵，用于进行变更操作
    private static String[][] gridCopy;

    // 存储即将被更改的坐标
    private static List<int[]> coordinates = new ArrayList<>();

    public static void main(String[] args) {
        // 读取输入的矩阵数据
        List<String> inputList = readInput();

        // 初始化矩阵（grid和gridCopy）
        initGrids(inputList);

        // 计算初始矩阵中 "NO" 的数量
        int noNums = countNoOccurrences();

        boolean flag = true;  // 标志，判断是否继续处理
        int day = 0;  // 记录天数

        // 只要还有 "NO" 需要处理并且可以进行改建，继续执行
        while (noNums != 0 && flag) {
            // 遍历所有 "YES" 的坐标，更新相邻的 "NO"
            for (int[] coordinate : findYesCoords()) {
                updateAdjElems(coordinate[0], coordinate[1]);
            }

            // 如果有更新的 "NO" 被改成了 "YES"
            if (!coordinates.isEmpty()) {
                // 更新 gridCopy，标记已改建区域
                updateGridCopy();

                // 减少改建的 "NO" 数量，并清空坐标列表
                noNums -= coordinates.size();
                coordinates.clear();

                // 增加一天
                day++;
            } else {
                // 如果没有改建，停止循环
                flag = false;
            }
        }

        // 输出最终结果：如果没有 "NO" 了，输出经过的天数，否则输出 -1
        printDayOrMinusOne(noNums, day);
    }

    // 读取输入的方法，返回包含每行数据的列表
    private static List<String> readInput() {
        List<String> inputList = new ArrayList<>();
        try (Scanner scanner = new Scanner(System.in)) {
            // 读取每一行直到遇到空行
            while (true) {
                String s = scanner.nextLine().trim(); // 读取一行并去除首尾空格
                if (s.isEmpty()) { // 如果输入为空行，则停止读取
                    break;
                }
                inputList.add(s);
            }
        }
        return inputList;
    }

    // 初始化 grid 和 gridCopy，gridCopy 用来存储修改后的状态
    private static void initGrids(List<String> inputList) {
        rows = inputList.size();  // 行数
        cols = inputList.get(0).split(" ").length;  // 列数，假设每行的元素数一致

        // 创建矩阵
        String[][] grid = new String[rows][cols];
        gridCopy = new String[rows][cols];  // 复制矩阵

        // 将输入的数据填充到 grid 和 gridCopy 中
        for (int i = 0; i < rows; i++) {
            String[] strings = inputList.get(i).split(" ");  // 按空格拆分每行
            System.arraycopy(strings, 0, grid[i], 0, cols);
            System.arraycopy(strings, 0, gridCopy[i], 0, cols);
        }
    }

    // 计算 "NO" 出现的次数
    private static int countNoOccurrences() {
        int count = 0;
        // 遍历 gridCopy，统计每行中 "NO" 的出现次数
        for (String[] row : gridCopy) {
            count += (int) Arrays.stream(row).filter(s -> s.equals("NO")).count();
        }
        return count;
    }

    // 更新相邻的 "NO" 为 "YES"
    private static void updateAdjElems(int i, int j) {
        // 定义四个方向：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 遍历四个方向
        for (int[] dir : directions) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];

            // 如果新坐标合法并且是 "NO"，则将其改为 "YES"
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
                    gridCopy[newRow][newCol].equals("NO")) {
                gridCopy[newRow][newCol] = "YES";  // 更改为 "YES"
                coordinates.add(new int[]{newRow, newCol});  // 将其坐标加入待处理队列
            }
        }
    }

    // 查找所有 "YES" 的坐标
    private static List<int[]> findYesCoords() {
        List<int[]> yesCoords = new ArrayList<>();
        // 遍历整个矩阵，查找 "YES" 的坐标
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (gridCopy[i][j].equals("YES")) {
                    yesCoords.add(new int[]{i, j});
                }
            }
        }
        return yesCoords;
    }

    // 更新 gridCopy，将已修改的区域标记为 "YES"
    private static void updateGridCopy() {
        for (int[] coordinate : coordinates) {
            gridCopy[coordinate[0]][coordinate[1]] = "YES";
        }
    }

    // 输出天数或 -1
    private static void printDayOrMinusOne(int noNums, int day) {
        // 如果没有 "NO" 了，输出天数，否则输出 -1
        System.out.println(noNums == 0 ? day : -1);
    }
}
